//
// Created by cheng on 2021/02/24.
// 已知二叉树的先序和中序遍历序列，输出二叉树的后序遍历的序列
//

#include "../Utils/MyUtil.h"
#include <vector>
#include <algorithm>

using namespace std;

void Solve(const vector<int>& pre, const vector<int>& in, vector<int>& post);

void Reconstruction( const vector<int>& pre, const vector<int>& in,
                     vector<int>& post, int left, int right);

static int position;

int main () {
    vector<int> pre = {1,2,3,4,5,6,7,8,9}, in = {3,2,5,4,6,1,8,7,9};
    vector<int> post; post.reserve(pre.size());
    MyUtil::PrintVector(pre, "先序遍历");
    MyUtil::PrintVector(in, "中序遍历");
    Solve(pre, in, post);
}

void
Solve(const vector<int> &pre, const vector<int> &in, vector<int> &post) {
    position = 0;
    Reconstruction(pre, in, post, 0, pre.size());
    MyUtil::PrintVector(post, "后序遍历");
}

void
Reconstruction(const vector<int> &pre, const vector<int> &in, vector<int> &post,
               int left, int right) {
    if (left >= right) {
        return;
    }
    // 当前的根结点
    int root = pre[position++];
    // 找到根结点在中序遍历中的位置
    int m = distance(in.begin(), find(in.begin(), in.end(), root));
    // 重建左右子树
    Reconstruction(pre, in, post, left, m);
    Reconstruction(pre, in, post, m+1, right);
    post.push_back(root);
}
